package datamining.algorithms.aprioriall;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;

/**
 * Main Apriori algorithm processing class
 * 
 * @author Kelvin
 */
public class Apriori {

        private static int countSup(List<ApriorModelData> data, ItemSet itemSet) {
                int count = 0;

                for (ApriorModelData m : data) {
                        Iterator<Item> itemIter = itemSet.getItems().iterator();
                        try {
                                Item current = itemIter.next();
                                for (Item item : m.getItems()) {
                                        if (item.equals(current)) {
                                                current = itemIter.next();
                                        } else if (item.compareTo(current) > 0) {
                                                break;
                                        }
                                }
                        } catch (NoSuchElementException e) {
                                count++;
                        }
                }

                return count;
        }

        public static Set<ItemSet> generateC1(List<ApriorModelData> data) {

                Set<ItemSet> ret = new TreeSet<ItemSet>();

                for (ApriorModelData md : data) {
                        for (Item item : md.getItems()) {
                                ItemSet is = new ItemSet();
                                is.getItems().add(item);
                                ret.add(is);
                        }
                }

                return ret;
        }

        public static Set<ItemSet> generateCn(int n, Set<ItemSet> lastFreqSeqs) {

                Set<ItemSet> ret = new TreeSet<ItemSet>();

                for (ItemSet is : lastFreqSeqs) {
                        boolean on = false;
                        label: for (ItemSet is2 : lastFreqSeqs) {
                                if (on) {
                                        Iterator<Item> seqIter = is.getItems().iterator();
                                        Iterator<Item> seqIter2 = is2.getItems().iterator();

                                        for (int i = 0; i < n - 2; i++) {
                                                if (!seqIter.next().equals(seqIter2.next())) {
                                                        continue label;
                                                }
                                        }
                                        ItemSet itemSet = new ItemSet(new TreeSet<Item>(is
                                                        .getItems()));
                                        itemSet.getItems().add(seqIter2.next());
                                        ret.add(itemSet);

                                } else if (is.equals(is2)) {
                                        on = true;
                                }
                        }
                }

                return ret;
        }

        public static Set<ItemSet> generateLn(List<ApriorModelData> data,
                        Set<ItemSet> candidates, double minSup) {

                Set<ItemSet> ret = new TreeSet<ItemSet>();
                double minSupCount = data.size() * minSup;

                for (ItemSet itemSet : candidates) {
                        int fitCount = countSup(data, itemSet);
                        if (fitCount >= minSupCount) {
                                ret.add(itemSet);
                        }
                }

                return ret;
        }

        public static Set<ItemSet> findAllFreqSets(List<ApriorModelData> data,
                        double minSup) {
                Set<ItemSet> ret = new TreeSet<ItemSet>();

                Set<ItemSet> candidates = generateC1(data);
                Set<ItemSet> freqItemSets = generateLn(data, candidates, minSup);

                ret.addAll(freqItemSets);

                for (int i = 2; freqItemSets.size() > 0; i++) {
                        ret.addAll(freqItemSets);
                        candidates = generateCn(i, freqItemSets);
                        freqItemSets = generateLn(data, candidates, minSup);
                }

                return ret;
        }
}
